home *** CD-ROM | disk | FTP | other *** search
/ Giga Games 1 / Giga Games.iso / net / go / games / optimal.sh < prev    next >
Encoding:
Linux/UNIX/POSIX Shell Script  |  1993-06-20  |  8.7 KB  |  411 lines

  1. #! /bin/sh
  2. # This is a shell archive, meaning:
  3. # 1. Remove everything above the #! /bin/sh line.
  4. # 2. Save the resulting text in a file.
  5. # 3. Execute the file with /bin/sh (not csh) to create:
  6. #    README
  7. #    opt1
  8. #    opt2
  9. #    opt3
  10. #    opt4
  11. #    opt5
  12. #    opt6
  13. #    opt7
  14. # This archive created: Mon Jan 20 18:43:13 1992
  15. export PATH; PATH=/bin:/usr/bin:$PATH
  16. if test -f 'README'
  17. then
  18.     echo shar: "will not over-write existing file 'README'"
  19. else
  20. cat << \SHAR_EOF > 'README'
  21. Path: milton!usenet.coe.montana.edu!rpi!usc!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!jvnc.net!darwin.sura.net!europa.asd.contel.com!uunet!mcsun!sun4nl!cwi.nl!tromp
  22. From: tromp@cwi.nl (John Tromp)
  23. Newsgroups: rec.games.go
  24. Subject: supposedly optimal play on small go-boards
  25. Message-ID: <5135@charon.cwi.nl>
  26. Date: 14 Jan 92 13:35:43 GMT
  27. Sender: news@cwi.nl
  28. Organization: CWI, Amsterdam
  29. Lines: 343
  30.  
  31. Recently, I got interested in discovering optimal play in go.
  32. That is, assuming the best play by both black and white, by how
  33. many points can black win the game? Since I have little hope of
  34. answering this question for the usual 19x19 board, or even the 9x9 one,
  35. I'll restrict my attention to board sizes smaller than 9x9.
  36.  
  37. The answer of course depends on the exact scoring rules used.
  38. The rules I use here are to count empty territory + prisoners, as
  39. the program mgt does it.
  40. Hopefully other readers will comment on changes in the outcome caused
  41. by different scoring rules (e.g. chinese).
  42.  
  43. Attached to this message is a shar file containing 7 files in mgt format.
  44. The first 6, on board sizes ranging from 1x1 through 6x6 represent what
  45. I believe to be optimal play, while the 7th is just a possible play on
  46. a 7x7 board, in which either white or black is likely to have missed a
  47. better move.
  48. Those lacking the mgt program can also follow the lines by numbering both
  49. axes of the board alphabetically.
  50.  
  51. The outcomes I get are:
  52.  
  53. boardsize            1x1  2x2  3x3  4x4  5x5  6x6  7x7
  54. margin for black       0    0    8    1   24    3    8
  55.  
  56. The first two are rather silly but included anyway for completeness.
  57. Note that on the 3x3 and 5x5 boards, black effectively dominates the whole
  58. board by playing in the center and thus wins by nxn-1. In the games, I have
  59. let white play as long as black is forced to reply.
  60.  
  61. I would like to have your opinion on these games, in particular
  62. suggestions for better lines in the 7x7 game. The 8x8 board may
  63. also be amenable to such analysis due to the symmetry. Still, it's not
  64. so obvious that one should start dividing the center, which in this
  65. case is relatively far from the edge.
  66.  
  67. Happy analysis!
  68.  
  69. -John Tromp, ~10 kyu (tromp@cwi.nl)
  70.  
  71.  
  72.  
  73.  
  74.  
  75. Path: milton!nntp.uoregon.edu!cs.uoregon.edu!mips!think.com!wupost!waikato.ac.nz!comp.vuw.ac.nz!canterbury.ac.nz!math!wft
  76. From: wft@math.canterbury.ac.nz (Bill Taylor)
  77. Newsgroups: rec.games.go
  78. Subject: Optimal play on small go-boards.
  79. Message-ID: <1992Jan20.182631.3508@csc.canterbury.ac.nz>
  80. Date: 20 Jan 92 05:26:30 GMT
  81. Organization: Department of Mathematics, University of Canterbury
  82. Lines: 59
  83. Nntp-Posting-Host: math.canterbury.ac.nz
  84.  
  85. tromp@cwi.nl (John Tromp) posted an article "supposedly optimal play on small
  86. go-boards" on 14 Jan 92.
  87.  
  88. I was hoping there would be some replies, but none so far, so here's mine.
  89.  
  90. John writes 
  91. > The outcomes I get are:
  92. >
  93. > boardsize            1x1  2x2  3x3  4x4  5x5  6x6  7x7
  94. > margin for black       0    0    8    1   24    3    8
  95.  
  96. He is using (empty spaces + prisoners) scoring, which is in fact neither
  97. Chinese nor Japanese. My comments will be directed mainly toward Chinese scoring,
  98. (as suggested by John), i.e. 1 point for all intersections filled or surrounded,
  99. (ignoring prisoners), which I understand is also official American scoring now
  100. as well. (It has been official here in N.Z. for many years). With this we get
  101.  
  102. boardsize           2x2  3x3  4x4  5x5  6x6  
  103. margin for black      1    9    2   25    4 
  104.  
  105. with the same moves as given by John. These figures are all one point more to
  106. black, (as is the case in 50% of normal games; interestingly for these small
  107. boards this happens in ALL cases, black always gets the last move.)
  108.                                                                a   b
  109. Only the case 2x2 needs a little extra comment. The full
  110. game should go (aa bb ba pass pass). Thus black is ahead    a  @ - .
  111. by one point, as in the diagram. White cannot improve with     |   |
  112. capture ab, otherwise black plays ba (NOT aa !), then       b  @ - O
  113. aa ba ab aa pass, and white cannot play, by the (Chinese 
  114. and American) no-repeat rule. These comments, and the cases 3x3 and 4x4, were
  115. given by James Davies, in his article "the Chinese rules of go", in GO WORLD
  116. of about late '77 or early '78.
  117.  
  118. The 4x4 case needs a little checking, but is fairly straightforward; (as Davies
  119. points out, this is in fact a zero-point tie in Japanese).           The 3x3
  120. and 5x5 cases are very simple, and could sensibly end after only one move, of
  121. course (especially the 3x3). The 6x6 case is more interesting; the line
  122. given by John is correct, as given in an introductory go book whose name
  123. I've unfortunately forgotten (if anyone has seen this book I'd be grateful for
  124. an email on this !). John gives cc dd dc cd bd be ed ee de ce fe ef ec bc bb
  125. ad ab ac fd df ff. This gives 4 (Chinese) to black, the best result. The moves
  126. for black are all forced (ignoring trivial symmetries); but White has some 
  127. interesting options that give the same final score with correct play. You
  128. might have some fun checking out the variant where white plays mirror-go for
  129. as long as he can, and black must find the correct way to break out of it.
  130.  
  131. As for the 7x7, I suspect John's answer of 8 (Chinese 9) is wrong. John gives
  132. a line starting dd ee ed de cd , then continuing much as in the 6x6 case, giving
  133. the result above. However I suspect black's 3rd move is wrong. With the more 
  134. aggressive 3rd move, ce, we get, for the whole game, in its most simple
  135. variant; dd ee ed de ce cf be bf fe ff fd bd cd ae bc ad ac af gf fg ge dg gg.
  136. Black wins by 15 (14 Japanese); but white may resist more strongly at various
  137. places, and it then becomes quite hard to check that black can maintain this
  138. result. I suspect that a fully detailed analysis would cover several pages to
  139. be reasonably convincing !
  140.  
  141. Anyway, all players are urged to try for themselves, and post their comments
  142. for us to see.
  143. ----------------------Pleasant plonking!------Bill Taylor--------------------
  144.  
  145. SHAR_EOF
  146. fi
  147. if test -f 'opt1'
  148. then
  149.     echo shar: "will not over-write existing file 'opt1'"
  150. else
  151. cat << \SHAR_EOF > 'opt1'
  152. (
  153. ;
  154. GaMe[1]
  155. VieW[]
  156. SiZe[1]
  157. Comment[Black: 0 + 0 = 0
  158.  
  159. White: 0 + 0 = 0
  160.  
  161. White wins by 0.]
  162. )
  163. SHAR_EOF
  164. fi
  165. if test -f 'opt2'
  166. then
  167.     echo shar: "will not over-write existing file 'opt2'"
  168. else
  169. cat << \SHAR_EOF > 'opt2'
  170. (
  171. ;
  172. GaMe[1]
  173. VieW[]
  174. SiZe[2]
  175. Comment[A supposedly optimal game.]
  176. ;
  177. Black[aa]
  178. ;
  179. Comment[Black: 0 + 0 = 0
  180.  
  181. White: 0 + 0 = 0
  182.  
  183. White wins by 0.]
  184. White[bb]
  185. )
  186. SHAR_EOF
  187. fi
  188. if test -f 'opt3'
  189. then
  190.     echo shar: "will not over-write existing file 'opt3'"
  191. else
  192. cat << \SHAR_EOF > 'opt3'
  193. (
  194. ;
  195. GaMe[1]
  196. VieW[]
  197. SiZe[3]
  198. Comment[A supposedly optimal game.]
  199. ;
  200. Black[bb]
  201. ;
  202. White[bc]
  203. ;
  204. Black[cb]
  205. ;
  206. White[ab]
  207. ;
  208. Comment[Black: 6 + 2 = 8
  209.  
  210. White: 0 + 0 = 0
  211.  
  212. Black wins by 8.]
  213. Black[ba]
  214. )
  215. SHAR_EOF
  216. fi
  217. if test -f 'opt4'
  218. then
  219.     echo shar: "will not over-write existing file 'opt4'"
  220. else
  221. cat << \SHAR_EOF > 'opt4'
  222. (
  223. ;
  224. GaMe[1]
  225. VieW[]
  226. SiZe[4]
  227. Comment[A supposedly optimal game.]
  228. ;
  229. Black[bb]
  230. ;
  231. White[cc]
  232. ;
  233. Black[cb]
  234. ;
  235. White[bc]
  236. ;
  237. Black[ac]
  238. ;
  239. White[db]
  240. ;
  241. Black[bd]
  242. ;
  243. White[ca]
  244. ;
  245. Black[cd]
  246. ;
  247. White[dc]
  248. ;
  249. Comment[Black: 2 + 0 = 2
  250.  
  251. White: 1 + 0 = 1
  252.  
  253. Black wins by 1.]
  254. Black[aa]
  255. )
  256. SHAR_EOF
  257. fi
  258. if test -f 'opt5'
  259. then
  260.     echo shar: "will not over-write existing file 'opt5'"
  261. else
  262. cat << \SHAR_EOF > 'opt5'
  263. (
  264. ;
  265. GaMe[1]
  266. VieW[]
  267. SiZe[5]
  268. Comment[A supposedly optimal game.]
  269. ;
  270. Black[cc]
  271. ;
  272. White[cd]
  273. ;
  274. Black[dc]
  275. ;
  276. White[bc]
  277. ;
  278. Black[bb]
  279. ;
  280. White[ad]
  281. ;
  282. Comment[Black: 21 + 3 = 24
  283.  
  284. White: 0 + 0 = 0
  285.  
  286. Black wins by 24.]
  287. Black[be]
  288. )
  289. SHAR_EOF
  290. fi
  291. if test -f 'opt6'
  292. then
  293.     echo shar: "will not over-write existing file 'opt6'"
  294. else
  295. cat << \SHAR_EOF > 'opt6'
  296. (
  297. ;
  298. GaMe[1]
  299. VieW[]
  300. SiZe[6]
  301. Comment[A supposedly optimal game.]
  302. ;
  303. Black[cc]
  304. ;
  305. White[dd]
  306. ;
  307. Black[dc]
  308. ;
  309. White[cd]
  310. ;
  311. Black[bd]
  312. ;
  313. White[be]
  314. ;
  315. Black[ed]
  316. ;
  317. White[ee]
  318. ;
  319. Black[de]
  320. ;
  321. White[ce]
  322. ;
  323. Black[fe]
  324. ;
  325. White[ef]
  326. ;
  327. Black[ec]
  328. ;
  329. White[bc]
  330. ;
  331. Black[bb]
  332. ;
  333. White[ad]
  334. ;
  335. Black[ab]
  336. ;
  337. White[ac]
  338. ;
  339. Black[fd]
  340. ;
  341. White[df]
  342. ;
  343. Comment[Black: 11 + 0 = 11
  344.  
  345. White: 6 + 2 = 8
  346.  
  347. Black wins by 3.]
  348. Black[ff]
  349. )
  350. SHAR_EOF
  351. fi
  352. if test -f 'opt7'
  353. then
  354.     echo shar: "will not over-write existing file 'opt7'"
  355. else
  356. cat << \SHAR_EOF > 'opt7'
  357. (
  358. ;
  359. GaMe[1]
  360. VieW[]
  361. SiZe[7]
  362. Comment[A supposedly optimal game.]
  363. ;
  364. Black[dd]
  365. ;
  366. White[ee]
  367. ;
  368. Black[ed]
  369. ;
  370. White[de]
  371. ;
  372. Black[cd]
  373. ;
  374. White[ce]
  375. ;
  376. Black[be]
  377. ;
  378. White[bf]
  379. ;
  380. Black[fe]
  381. ;
  382. White[ff]
  383. ;
  384. Black[fd]
  385. ;
  386. White[bd]
  387. ;
  388. Black[bc]
  389. ;
  390. White[ae]
  391. ;
  392. Black[ac]
  393. ;
  394. White[gf]
  395. ;
  396. Black[ad]
  397. ;
  398. White[be]
  399. ;
  400. Comment[Black: 20 + 0 = 20
  401.  
  402. White: 11 + 1 = 12
  403.  
  404. Black wins by 8.]
  405. Black[ge]
  406. )
  407. SHAR_EOF
  408. fi
  409. exit 0
  410. #    End of shell archive
  411.